﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using FCA.Dto;

namespace FCA.Algorithm {
    public class CLICL {
        public Lattice L { get; set; }
        public IndexTable FirstNodes { get; set; }

        public CLICL() {
            L = new Lattice();
            FirstNodes = new IndexTable();
        }

        public void InitLattice(int tid, ItemSet t) {
            //the first itemset            
            Concept root = new Concept();
            root.ID = 0;
            root.Items = new ItemSet();
            L.AddConceptWithID(root);
            L.RootNodeID = 0;
            L.Concepts[L.RootNodeID].Tids.Add(1);

            Concept lastNode = new Concept();
            lastNode.ID = 0;
            lastNode.Items = t;
            //lastNode.Tids.Add(1);
            L.AddConcept(lastNode);
            L.LastNodeID = 1;

            Concept firstNode = new Concept();
            firstNode.ID = 1;
            firstNode.Items = t;
            firstNode.Tids.Add(1);
            L.AddConcept(firstNode);

            root.AddChild(firstNode);
            firstNode.AddChild(lastNode);

            foreach (int item in t.Items) {
                FirstNodes.AddIndex(item, 2);
            }
        }
        //Build Base lattice

        //Delete transaction

        /// <summary>
        /// Add transaction to the current Lattice L 
        /// </summary>
        /// <param name="tid">transaction id</param>
        /// <param name="t">item set of the transaction to insert</param>        
        public void AddTransaction(int tid, ItemSet t) {
            //update lastNode
            L.Concepts[L.LastNodeID].Items = L.Concepts[L.LastNodeID].Items.UnionWith(t);
            //update root node
            L.Concepts[L.RootNodeID].Tids.Add(tid);
            //create a new Node N with In = t
            AddTransaction(new TidSet(new HashSet<int>() { tid }), t);

        }

        public void AddTransaction(TidSet tids, ItemSet t) {
            Concept n = new Concept();
            n.Items = t;
            foreach (int tid in tids.Tids) {
                n.Tids.Add(tid);
            }

            bool isAdded = false;
            //for all item i in t in L do
            foreach (int i in t.Items) {
                int index = FirstNodes.GetFirstNode(i);
                if (index == -1) {
                    if (isAdded) {
                        FirstNodes.AddIndex(i, n.ID);
                    }
                    continue;
                }
                Concept fi = L.Concepts[index];
                //if Fi is ancestor of N then (this is the common case)
                if (fi.Items.IsAncestorOf(n.Items)) {
                    //find child and parents of N among the descendants of fi
                    Case1(n, fi, ref isAdded);
                } else if (fi.Items.IsDescendantOf(n.Items)) {
                    //if Fi is descendant of N 
                    //child of N is Fi and parents of N are among the ancestors of fi
                    Case2(n, fi, i, ref isAdded);

                } else {
                    Case3(n, fi, i, ref isAdded);
                }
            }
            if (n.ChildrenID.Count == 0) {
                n.AddChild(L.Concepts[L.LastNodeID]);
            }
            foreach (int item in t.Items) {
                if (!FirstNodes.ContainsKey(item)) {
                    FirstNodes.AddIndex(item, n.ID);
                }
            }
        }


        #region Case 3
        private void Case3(Concept n, Concept fi, int i, ref  bool isAdded) {
            //if common parent X of Fi and N exist in L then
            //  parent of N is X and child of N is among descendants of fi
            //else
            //  create a new node X where Ix = Ifi and In
            //  parent of N is X and child of N is among descendants of Fi
            //  children of X are fi and some ancestor of N
            //  parents of X are among the ancestors of fi
            //  if X is neither ancestor nor descendant of node Y thuoc L and Ix and Iy khac rong
            //  then
            //      create a new node U such that Iu = Iy and Ix
            //      find child and parents of node U
            //  end if
            //end if

            //Case 3: Fi is neither ancestor nor descendent of N.  (Ifi not in In, Ifi not cover In, Ifi /\ In <> null)
            //In this case, common parent of Fi and N with closed itemset as X = Ifi /\ In may exists in L or it may not exist
            if (!isAdded) {
                isAdded = true;
                L.AddConcept(n);
            }
            Concept x = new Concept();
            x.Items = fi.Items.IntersectWith(n.Items);

            Concept t = ItemSetIsExistedInLattice(x.Items);
            TidSet tids = fi.Tids.UnionWith(n.Tids);
            //Case 3.1: Ifi /\ In exists as closed itemset of a node X in L
            //If such a node X existed in L then 
            //  X is parent of N. 
            //  Child of N is among the descendants of Fi. We check all the descendants of Fi till we find a node
            //      whose closed itemset is minimal superset of closed itemset of N, that node becomes the child of N
            if (t != null) {
                t.Tids = tids;

                Case3_1(n, fi, t, i);
            } else {
                //Case 3.2: Ifi /\ In does not exists as closed itemset of a node X in L
                //A new node X is created with Ix = Ifi /\ In and added to L. 
                //  X becomes the parent of N 
                //  and child of N is among the descendants of Fi.
                //      We check all the descendants of Fi till we get a node
                //          those closed itemset is minimal superset of closed itemset of N, that node becomes the child of N.
                x.Tids = tids;
                Case3_2_1_FindParentAndChildOfXInDescendantsOfFi(n, fi, x);

                //Next step is to find the child and parents of X.
                //  Parents of X are among the ancestors of Fi
                //      We check all the ancestors of Fi. If we get a node Y such that 
                //          closed itemset of Y is superset of X 
                //          and closed itemset of one of the parent Z of Y is subset of X
                //          then Z becomes the parent of X
                //          and Y is child of X
                //  If we find an ancestor Y of Fi such that Y is neither ancestor nor descendent of X, then
                //      a new node U is created with Iu = Iy /\ Ix.
                //      Then we repeat the process to find child and parents of node U 
                x.AddChild(fi);
                FirstNodes.UpdateIndexIfExisted(i, x.ID, fi.ID);
                HashSet<int> checkedConceptIds = new HashSet<int>();
                Case3_2_2_FindChildAndParentOfXInAncestorFi(x, fi, checkedConceptIds);
                //Case3_2_2_Wrong(x, fi, fi, i);
            }
        }

        //private void Case1_FindParentOfNInDescendantsFi(Concept n, Concept currentNode) {

        private void Case3_2_2_FindChildAndParentOfXInAncestorFi(Concept x, Concept currentNode, HashSet<int> checkedConceptIds) {
            foreach (Concept parent in currentNode.GetParents(L)) {
                if (checkedConceptIds.Contains(parent.ID) || x.ID == parent.ID) { continue; }
                if (parent.Items.IsSuperSetOf(x.Items)) {
                    //all parents of parent isn't superset of x => add parent as x parent
                    bool noParentOfParentIsSuperSet = true;
                    foreach (Concept parentOfParent in parent.GetParents(L)) {
                        if (x.ID == parentOfParent.ID) { continue; }
                        if (parentOfParent.Items.IsSuperSetOf(x.Items)) {
                            noParentOfParentIsSuperSet = false;
                            break;
                        } else if (parentOfParent.Items.IsSubSetOf(x.Items)) {
                            //remove connection between child and childOfChild
                            parent.RemoveParent(parentOfParent);
                            parent.AddParent(x);
                            x.AddParent(parentOfParent);
                            checkedConceptIds.Add(parentOfParent.ID);
                            checkedConceptIds.Add(parent.ID);
                            //break;
                        }

                    }
                    if (noParentOfParentIsSuperSet) {
                        //=> parent is superSet of x
                        parent.AddParent(x);
                        checkedConceptIds.Add(parent.ID);
                    } else {
                        //Case1_FindParentOfNInDescendantsFi(x, parent, checkedConceptIds);
                    }
                } else if (parent.Items.IsSubSetOf(x.Items)) {
                    bool nochildOfParentIsSuperSet = true;
                    foreach (Concept childOfParent in parent.GetChildren(L)) {
                        if (x.ID == childOfParent.ID) { continue; }
                        if (childOfParent.Items.IsSubSetOf(x.Items)) {
                            nochildOfParentIsSuperSet = false;
                            break;
                        } else
                            if (childOfParent.Items.IsSuperSetOf(x.Items)) {
                                childOfParent.RemoveParent(parent);
                                childOfParent.AddParent(x);
                                x.AddParent(parent);
                                checkedConceptIds.Add(parent.ID);
                                checkedConceptIds.Add(childOfParent.ID);
                            }
                    }

                    if (nochildOfParentIsSuperSet) {
                        //=> child is subset of N
                        x.AddParent(parent);
                        checkedConceptIds.Add(parent.ID);
                    }
                } else {

                    Concept newNode = new Concept();
                    newNode.Items = x.Items.IntersectWith(parent.Items);
                    Concept existedNode = ItemSetIsExistedInLattice(newNode.Items);
                    if (newNode.Items.Length() > 0 && existedNode == null) {
                        AddTransaction(x.Tids.UnionWith(parent.Tids), newNode.Items);
                    } else if (existedNode != null) {
                        x.AddParent(existedNode);
                        checkedConceptIds.Add(existedNode.ID);
                    }
                }
                Case3_2_2_FindChildAndParentOfXInAncestorFi(x, parent, checkedConceptIds);
            }

        }

        private void Case3_2_1_FindParentAndChildOfXInDescendantsOfFi(Concept n, Concept fi, Concept x) {
            //Case 3.2: Ifi /\ In does not exists as closed itemset of a node X in L
            //A new node X is created with Ix = Ifi /\ In and added to L. 
            //  X becomes the parent of N 
            //  and child of N is among the descendants of Fi.
            //      We check all the descendants of Fi till we get a node
            //          those closed itemset is minimal superset of closed itemset of N, that node becomes the child of N.
            L.AddConcept(x);

            foreach (Concept parent in n.GetParents(L)) {
                if (parent.Items.IsSubSetOf(x.Items)) {
                    n.RemoveParent(parent);
                    //we don't metion what is x parent now!!!
                }
            }
            n.AddParent(x);
            Case3_1_FindChildOfNInDescendantsOfFi(n, fi);
        }

        private void Case3_1(Concept n, Concept fi, Concept x, int i) {
            //Case 3.1: Ifi /\ In exists as closed itemset of a node X in L
            //If such a node X existed in L then 
            //  X is parent of N. 
            //  Child of N is among the descendants of Fi. We check all the descendants of Fi till we find a node
            //      whose closed itemset is minimal superset of closed itemset of N, that node becomes the child of N

            n.AddParent(x);
            //
            FirstNodes.UpdateIndexIfExisted(i, x.ID, fi.ID);
            if (x.ChildrenID.Count == 1) {
                //in this case, x is parent of lower node => so now n is parent of lower node
                return;
            }
            //Case3_1_FindChildOfNInDescendantsOfFi(tid, n, fi);

            foreach (Concept desFi in fi.GetChildren(L)) {
                Case3_1_FindChildOfNInDescendantsOfFi(n, desFi);
                //Case3_1_FindChildOfNInDescendantsOfFi(n, desFi);
            }

        }

        private void Case3_1_FindChildOfNInDescendantsOfFi(Concept n, Concept currentNode) {
            foreach (Concept child in currentNode.GetChildren(L)) {
                if (child.ID == n.ID) { continue; }
                if (child.Items.IsSuperSetOf(n.Items)) {
                    n.AddChild(child);
                    //fore
                } else {
                    Case3_1_FindChildOfNInDescendantsOfFi(n, child);
                }

            }
        }

        /// <summary>
        /// Child of N is among the descendants of Fi. We check all the descendants of Fi till we find a node
        /// whose closed itemset is minimal superset of closed itemset of N, that node becomes the child of N
        /// </summary>
        /// <param name="tid"></param>
        /// <param name="n"></param>
        /// <param name="fi"></param>
        /// <param name="resultConceptID"></param>
        /// <param name="min"></param>
        private void Case3_1_FindChildOfNInDescendantsOfFi(int tid, Concept n, Concept fi, ref int resultConceptID, ref int min) {
            //  Child of N is among the descendants of Fi. We check all the descendants of Fi till we find a node
            //      whose closed itemset is minimal superset of closed itemset of N, that node becomes the child of N

            foreach (Concept child in fi.GetChildren(L)) {
                if (child.Items.IsSuperSetOf(n.Items)) {
                    if (min < (child.Items.Length() - n.Items.Length())) {
                        min = child.Items.Length() - n.Items.Length();
                        resultConceptID = child.ID;
                    }
                }
                Case3_1_FindChildOfNInDescendantsOfFi(tid, n, child, ref resultConceptID, ref min);
            }
        }
        #endregion

        #region Case 2
        private void Case2(Concept n, Concept fi, int i, ref bool isAdded) {
            if (!isAdded) {
                L.AddConcept(n);
                isAdded = true;
            }

            //Fi is the child of N and First Node Fi corresponding to i in In is set to N.
            n.AddChild(fi);
            FirstNodes.UpdateIndexIfExisted(i, n.ID, fi.ID);

            HashSet<int> checkedConceptIds = new HashSet<int>();
            Case2_FindParentOfNInAncestorsFi(n, fi, checkedConceptIds);
        }

        private void Case2_FindParentOfNInAncestorsFi(Concept n, Concept fi, HashSet<int> checkedConceptIds) {
            foreach (Concept parent in fi.GetParents(L)) {
                if (checkedConceptIds.Contains(parent.ID) || n.ID == parent.ID) { continue; }
                if (parent.Items.IsSubSetOf(n.Items)) {
                    bool nochildOfParentIsSuperSet = true;
                    foreach (Concept childOfParent in parent.GetChildren(L)) {
                        if (n.ID == childOfParent.ID) { continue; }
                        if (childOfParent.Items.IsSubSetOf(n.Items)) {
                            nochildOfParentIsSuperSet = false;
                            break;
                        } else
                            if (childOfParent.Items.IsSuperSetOf(n.Items)) {
                                childOfParent.RemoveParent(parent);
                                childOfParent.AddParent(n);
                                n.AddParent(parent);
                                checkedConceptIds.Add(parent.ID);
                                checkedConceptIds.Add(childOfParent.ID);
                            }
                    }

                    if (nochildOfParentIsSuperSet) {
                        //=> child is subset of N
                        n.AddParent(parent);
                        checkedConceptIds.Add(parent.ID);
                    }
                } 
                Case3_2_2_FindChildAndParentOfXInAncestorFi(n, parent, checkedConceptIds);
            }
        }

        private void Case2Wrong(Concept n, Concept fi, int i, ref bool isAdded) {
            //child of N is Fi and parents of N are among the ancestors of fi
            if (!isAdded) {
                L.AddConcept(n);
                isAdded = true;
            }
            //Fi is the child of N and First Node Fi corresponding to i in In is set to N.
            n.AddChild(fi);
            FirstNodes.UpdateIndexIfExisted(i, n.ID, fi.ID);

            //We search among the parents of Fi for finding parents of N.
            //  If closed itemset of those parents is subset of In, then those parents are parents of N also.
            //  If no such parent exist then top node T of L is the parent of N
            bool hasParent = false;
            foreach (Concept parentFi in n.GetParents(L)) {
                if (parentFi.Items.IsSubSetOf(n.Items)) {
                    n.AddParent(parentFi);
                    parentFi.RemoveChild(fi);
                    hasParent = true;
                }
            }
            if (!hasParent) {
                L.Concepts[L.RootNodeID].AddChild(n);
            }

        }
        #endregion

        #region Case 1
        private void Case1(Concept n, Concept fi, ref bool isAdded) {
            //find child and parents of N among the descendants of fi

            //child of N is among the descendants of Fi. Parent(s) of N is either the node Fi itself or some of
            //Fi's descendant(s).

            //If closed itemsets of any of the child node X of Fi is superset of In then {
            //  Fi is the parent of N 
            //  X is the child node of N
            //}
            List<Concept> children = fi.GetChildren(L);
            if (!isAdded) {
                L.AddConcept(n);
                isAdded = true;
            }
            foreach (Concept x in children) {
                if (x.ID != n.ID && x.Items.IsSuperSetOf(n.Items)) {
                    if (!isAdded) {
                        L.AddConcept(n);
                        isAdded = true;
                    }
                    n.AddParent(fi);
                    //n.AddChild(x);

                    x.RemoveParent(fi);
                    x.AddParent(n);
                    return;
                }
            }
            HashSet<int> checkedConceptIds = new HashSet<int>();
            Case1_FindParentOfNInDescendantsFi(n, fi, checkedConceptIds);
        }

        private void Case1_FindParentOfNInDescendantsFi(Concept n, Concept currentNode, HashSet<int> checkedConceptIds) {
            foreach (Concept child in currentNode.GetChildren(L)) {
                if (checkedConceptIds.Contains(child.ID) || n.ID == child.ID) { continue; }
                if (child.Items.IsSubSetOf(n.Items)) {
                    bool noChildOfChildIsSubSet = true;
                    foreach (Concept childOfChild in child.GetChildren(L)) {
                        if (n.ID == childOfChild.ID) { continue; }
                        if (childOfChild.Items.IsSubSetOf(n.Items)) {
                            noChildOfChildIsSubSet = false;
                            break;
                        } else if (childOfChild.Items.IsSuperSetOf(n.Items)) {
                            //remove connection between child and childOfChild
                            child.RemoveChild(childOfChild);
                            child.AddChild(n);
                            n.AddChild(childOfChild);
                            //break;
                            checkedConceptIds.Add(childOfChild.ID);
                            checkedConceptIds.Add(child.ID);
                        }

                    }
                    if (noChildOfChildIsSubSet) {
                        //=> child is subset of N
                        child.AddChild(n);
                        checkedConceptIds.Add(child.ID);
                    } else {
                        //Case1_FindParentOfNInDescendantsFi(n, child, checkedConceptIds);
                    }
                } else if (child.Items.IsSuperSetOf(n.Items)) {
                    bool noParentOfChildIsSuperSet = true;
                    foreach (Concept parentOfChild in child.GetParents(L)) {
                        if (n.ID == parentOfChild.ID) { continue; }
                        if (parentOfChild.Items.IsSuperSetOf(n.Items)) {
                            noParentOfChildIsSuperSet = false;
                            break;
                        } else
                            if (parentOfChild.Items.IsSubSetOf(n.Items)) {
                                parentOfChild.RemoveChild(child);
                                parentOfChild.AddChild(n);
                                n.AddChild(child);
                                checkedConceptIds.Add(child.ID);
                                checkedConceptIds.Add(parentOfChild.ID);
                            }
                    }

                    if (noParentOfChildIsSuperSet) {
                        //=> child is subset of N
                        n.AddChild(child);
                        checkedConceptIds.Add(child.ID);
                    }
                } else {
                    //truong hop cua ab ne
                    Concept newNode = new Concept();
                    newNode.Items = n.Items.IntersectWith(child.Items);

                    Concept existedNode = ItemSetIsExistedInLattice(newNode.Items);
                    if (newNode.Items.Length() > 0 && existedNode == null) {
                        AddTransaction(n.Tids.UnionWith(child.Tids), newNode.Items);
                    } else if (existedNode != null) {
                        n.AddParent(existedNode);
                        checkedConceptIds.Add(existedNode.ID);
                    }
                }
                Case1_FindParentOfNInDescendantsFi(n, child, checkedConceptIds);
            }
        }
        #endregion

        internal Concept ItemSetIsExistedInLattice(ItemSet itemSet) {
            foreach (int itemID in itemSet.Items) {
                if (FirstNodes.Indexs.ContainsKey(itemID)) {

                    int conceptID = FirstNodes.Indexs[itemID];
                    if (L.Concepts.ContainsKey(conceptID)) {
                        Concept curConcept = L.Concepts[conceptID];
                        if (curConcept.Items.IsEqual(itemSet)) {
                            return L.Concepts[conceptID];

                        }
                    }
                    int id = -1;
                    FindItemInDescendants(L.Concepts[conceptID], itemSet, ref id);
                    if (id != -1 && L.Concepts.ContainsKey(id)) {
                        return L.Concepts[id];
                    }
                }
            }
            return null;
        }

        private void FindItemInDescendants(Concept curConcept, ItemSet itemSet, ref int id) {
            if (id != -1) {
                return;
            }

            //int curIntersectCount = curConcept.Items.IntersectWith(itemSet).Length();

            foreach (Concept child in curConcept.GetChildren(L)) {
                if (child.Items.IsEqual(itemSet)) {
                    id = child.ID;
                    return;
                } else if (child.Items.IsSubSetOf(itemSet)) {
                    FindItemInDescendants(child, itemSet, ref id);
                    //int childIntersectCount = curConcept.Items.IntersectWith(itemSet).Length();
                    //if (childInter

                }
            }

        }


    }
}
